package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 各种排序
 *
 * @author: trtan
 * @date: 2021-06-09 14:55
 **/
public class SortUtils {
    /**
     * 快速排序
     * @param array 要排序的数组
     * @param L 左边界
     * @param R 右边界
     * @param op 升序还是降序 1升序，2降序
     * @return void
     * @author trtan
     * @date 2021/6/9 15:00
     */
    public static void quick_sort(int[] array, int L, int R, int op) {
        if (L >= R) {
            return;
        }
        int l = L, r = R;
        int base = array[L];
        while (l < r) {
            // 升序
            if (op == 1) {
                // 把右边小于base的挪到左边
                while (l < r && array[r] >= base) {
                    r--;
                }
                array[l] = array[r];
                // 把左边大于base的挪到右边
                while (l < r && array[l] <= base) {
                    l++;
                }
            }
            // 降序
            else {
                //把右边大于base的挪到左边
                while (l < r && array[r] <= base) {
                    r--;
                }
                array[l] = array[r];
                //把左边小于base1的挪到右边
                while (l < r && array[l] >= base) {
                    l++;
                }
            }
            array[r] = array[l];
        }
        //分割位置设置为base
        array[l] = base;
        //以l分割分别对左右递归进行判断
        quick_sort(array, L, l - 1, op);
        quick_sort(array, l + 1, R, op);
    }

    /**
     * 调整堆
     * @param array 以数组代替堆结构
     * @param k 堆当前元素
     * @param n 堆大小
     * @param op 大顶堆还是小顶堆 1大顶堆 2小顶堆
     * @return void
     * @author trtan
     * @date 2021/6/9 15:15
     */
    private static void adjust_heap(int[] array, int k, int n, int op) {
        int now = array[k];
        for (int left = k * 2 + 1; left < n; left = left * 2 + 1) {
            int right = left + 1;
            int node = left;
            if (right < n) {
                // 大顶堆 取左右儿子大的那个交换
                if (op == 1) {
                    if (array[left] < array[right]) {
                        node = right;
                    }
                }
                // 小顶堆 取左右儿子较小的那个
                else {
                    if (array[left] > array[right]) {
                        node = right;
                    }
                }
            }
            //与当前点比较大小
            if (op == 1) {
                if (array[node] > now) {
                    array[k] = array[node];
                    k = node;
                } else {
                    break;
                }
            } else {
                if (array[node] < now) {
                    array[k] = array[node];
                    k = node;
                } else {
                    break;
                }
            }
            left = node;
        }
        array[k] = now;
    }

    /**
     * 堆排序
     * @param array 要排序的数组
     * @param op 升序还是降序 1升序 2降序
     * @return void
     * @author trtan
     * @date 2021/6/9 15:17
     */
    public static void heap_sort(int[] array, int op) {
        // 通过数组构建堆 从第一个非叶子节点调整使其满足堆结构
        for (int i = array.length / 2 - 1; i >= 0 ; i--) {
            adjust_heap(array, i, array.length, op);
        }

        //进行排序， 每次取堆顶元素放到最后面，再调整
        for (int i = array.length - 1; i > 0; i--) {
            int tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            adjust_heap(array, 0, i, op);
        }
    }

    /**
     * 归并排序
     * @param array 要排序的数组
     * @param L 左端点
     * @param R 右端点
     * @param op 升序还是降序 1升序 2降序
     * @return void
     * @author trtan
     * @date 2021/6/9 16:31
     */
    public static void merge_sort(int[] array, int L, int R, int op) {
        if (L + 1 >= R) {
            return;
        }
        // 划分左右 分而治之
        int mid = (L + R) / 2;
        merge_sort(array, L, mid, op);
        merge_sort(array, mid, R, op);
        // 合并小的 递归时不断合并为整个数组
        int l_1 = L, l_2 = mid;
        List<Integer> list = new ArrayList<>();
        while (l_1 < mid && l_2 < R) {
            if (array[l_1] < array[l_2]) {
                if (op == 1) {
                    list.add(array[l_1++]);
                } else {
                    list.add(array[l_2++]);
                }
            } else {
                if (op == 1) {
                    list.add(array[l_2++]);
                } else {
                    list.add(array[l_1++]);
                }
            }
        }
        while (l_1 < mid) {
            list.add(array[l_1++]);
        }
        while (l_2 < R) {
            list.add(array[l_2++]);
        }
        for (int i = L; i < R; i++) {
            array[i] = list.get(i - L);
        }
    }

    /**
     * 冒泡排序 每次交换两个相邻的数字，一遍操作后，最后一个数字定为最大或最小值
     * @param array 要排序的数组
     * @param op 1升序 2降序
     * @return void
     * @author trtan
     * @date 2021/6/9 16:41
     */
    public static void bubble_sort(int[] array, int op) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                // 升序
                if (op == 1) {
                    if (array[j] > array[j + 1]) {
                        int tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                    }
                } else {
                    if (array[j] < array[j + 1]) {
                        int tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                    }
                }
            }
        }
    }

    /**
     * 插入排序 维护前i个数字升序或降序，每次将第i个数字插入到指定位置
     * @param array 要排序的数组
     * @param op 1 升序 2 降序
     * @return void
     * @author trtan
     * @date 2021/6/9 16:41
     */
    public static void insert_sort(int[] array, int op) {
        for (int i = 1; i < array.length; i++) {
            int base = array[i];
            int k = i;
            // 寻找需要插入的位置
            for (int j = 0; j < i; j++) {
                if (op == 1) {
                    if (array[j] > base) {
                        k = j;
                        break;
                    }
                } else {
                    if (array[j]< base) {
                        k = j;
                        break;
                    }
                }
            }
            //将k后面的往后挪，把array[i]插入k位置
            for (int j = i; j > k; j--) {
                array[j] = array[j - 1];
            }
            array[k] = base;
        }
    }

    /**
     * 选择排序 每遍操作选取一个最大或最小值和第i个数交换
     * @param array
     * @param op 1 升序 2降序
     * @return void
     * @author trtan
     * @date 2021/6/9 16:41
     */
    public static void select_sort(int[] array, int op) {
        for (int i = 0; i < array.length; i++) {
            int max_pos = i;
            for (int j = i; j < array.length; j++) {
                // 升序
                if (op == 1) {
                    if (array[j] < array[max_pos]) {
                        max_pos = j;
                    }
                } else {
                    // 降序
                    if (array[j] > array[max_pos]) {
                        max_pos = j;
                    }
                }
            }
            if (max_pos != i) {
                int tmp = array[max_pos];
                array[max_pos] = array[i];
                array[i] = tmp;
            }
        }
    }


}
